1. Field of the Invention
The present invention relates to methods and systems for analyzing genetic algorithms and, more particularly, to methods and systems for analyzing control parameters of genetic algorithms and for analyzing the genetic algorithm""s parent class of evolutionary algorithms.
2. Description of the Related Art
Evolutionary algorithms (EAs), including genetic algorithms, have been used to determine optimal solutions to complex problems. U.S. Pat. No. 5,848,403, for example, describes the use of EAs to generate resource schedules for performing various tasks. To solve such problems, EAs start by generating an initial set of solutions to the problem. The EA then cyclically evaluates the quality of each solution using an objective function, selects those solutions having a relatively higher quality level, and alters the selected solutions. In this way, the EA eventually converges to an optimal solution after a number of iterations.
Several types of control parameters affect the speed, quality, and solution characteristics of such an EA system. While not an exhaustive list, these control parameters include: (1) the number of evaluations used to converge to the final result; (2) the population size of the initial set of solutions; and (3) the weighting factors of an objective function used to test the quality of each solution. Each of these control parameters will be described below.
The EA performs a number of evaluations to converge to the final recognition result. Typically, a programmer predefines the number of evaluations that the EA system will perform. Roughly speaking, the greater the number of evaluations, the higher the quality (as measured by the objective function) of the final result. However, the processing resource requirements increase along with the number of evaluations performed by the EA system. Thus, the programmer should select a number of evaluations that strikes the proper balance between processing resources and quality of the EA system""s results.
The population size of the initial number of solutions also affects the speed and quality of the EA system. In particular, a larger population size provides better initial coverage of the solution space to the problem at hand. Thus, the EA may be more likely to find higher quality solutions when converging to the final result. On the other hand, a smaller initial population size may provide enough quality, while allowing the EA system to converge at a faster rate. Thus, the programmer should also carefully choose the number of initial solutions when balancing speed and quality constraints.
As known in the art, the EA system uses an objective function to measure interesting properties of each solution during the convergence process. The objective function may be any function that returns a numerical value. This value measures the quality of each potential solution. Based on the value of the objective function, the typical EA system selects the higher quality solutions, alters the selected solutions, and then repeats the entire cycle. In this way, the EA system converges to an optimal final result.
For illustrative purposes, an objective function is described that consists of a linear combination of several weighted subfunctions. Typically, each subfunction measures the quality of a possible solution in terms of a single property or characteristic of the problem at hand. For the scheduling problem described in U.S. Pat. No. 5,848,403, for example, the properties may be the distance between tasks, the time to achieve each task, labor costs, or customer satisfaction. The equation below describes an exemplary objective function:
F(x)=w0f0(x)+w1f1(x) . . . +wNxe2x88x921fNxe2x88x921(x)
where:
x represents a possible solution to the problem;
fi(x) represents a subfunction for measuring the ith property of the problem; and
wi represents a bias weight for subfunction fi(x), such that 0xe2x89xa6wixe2x89xa61.
Thus, a user can bias the EA to produce solutions that emphasize certain properties by changing the relative values of the bias weights applied to each subfunction. In this way, a programmer can choose to emphasize the relative importance of an individual subfunction when evaluating the quality of each possible solution. These bias weights may be viewed as input parameters, or control parameters, to the EA system.
Currently, programmers have no general purpose, analytical or empirical method to predict how varying the values of any of the above control parameters will affect the final result of the EA system. Each parameter may affect the final result to a different degree. Also, the effect of varying a particular parameter differs between different applications of an EA. Additionally, parameters may interact, such that the effect of varying one parameter may depend upon the current value of other parameters. Thus, a programmer must often resort to a trial-and-error approach to xe2x80x9ctunexe2x80x9d the parameters. Such an ad hoc approach, however, is inefficient, difficult to analyze, and difficult to reproduce.
Thus, it is desired to have a standardized system and method for analyzing EAs. In particular, it is desirable to have a system and method that can analyze how changing a control parameter value affects the response of an EA.
Systems and methods consistent with the present invention analyze control parameters of an evolutionary algorithm to thereby allow a programmer to understand the effects of changing control parameter values and to efficiently select new values for the control parameters.
In accordance with the purposes of the invention as embodied and broadly described herein, a system and method consistent with the present invention evaluates evolutionary algorithms. The system determines the value of a control parameter that controls the operation of the evolutionary algorithm. The system also executes the evolutionary algorithm according to the determined value of the control parameter to obtain a response value, and determines an effect vector describing how a change in the value of the control parameter affects the response value.
Both the foregoing general description and the following detailed description are exemplary and are intended to provide further explanation of the invention as claimed.